home *** CD-ROM | disk | FTP | other *** search
/ Hot Super Models / Hot Super Models.iso / unix / x11 / xv200.tar / xv-2.00 / xv24to8.c < prev    next >
C/C++ Source or Header  |  1992-01-02  |  25KB  |  1,025 lines
  1. /*
  2.  * xv24to8.c  -  contains the 24-to-8-bit Conv24to8 procedure
  3.  *
  4.  * The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
  5.  * previously).  The image will be a w * h * 3 byte array of
  6.  * bytes.  The image will be arranged with 3 bytes per pixel (in order
  7.  * R, G, and B), pixel 0 at the top left corner.  (As normal.)
  8.  * The procedure also takes a maximum number of colors to use (numcols)
  9.  *
  10.  * The Conv24to8 procedure will set up the following:  it will allocate and
  11.  * create 'pic', a pWIDE*pHIGH 8-bit picture.  it will set up pWIDE and pHIGH.
  12.  * it will load up the r[], g[], and b[] colormap arrays.  it will NOT 
  13.  * calculate numcols, since the cmap sort procedure has to be called anyway
  14.  *
  15.  * Conv24to8 returns '0' if successful, '1' if it failed (presumably on a 
  16.  * malloc())
  17.  *
  18.  * contains:
  19.  *   Cont24to8()
  20.  *   Init24to8()
  21.  */
  22.  
  23. /*
  24.  * Copyright 1989, 1990, 1991, 1992 by John Bradley and
  25.  *                       The University of Pennsylvania
  26.  *
  27.  * Permission to use, copy, and distribute for non-commercial purposes,
  28.  * is hereby granted without fee, providing that the above copyright
  29.  * notice appear in all copies and that both the copyright notice and this
  30.  * permission notice appear in supporting documentation.
  31.  *
  32.  * The software may be modified for your own purposes, but modified versions
  33.  * may not be distributed.
  34.  *
  35.  * This software is provided "as is" without any expressed or implied warranty.
  36.  *
  37.  * The author may be contacted via:
  38.  *    US Mail:   John Bradley
  39.  *               GRASP Lab, Room 301C
  40.  *               3401 Walnut St.
  41.  *               Philadelphia, PA  19104
  42.  *
  43.  *    Phone:     (215) 898-8813
  44.  *    EMail:     bradley@cis.upenn.edu
  45.  */
  46.  
  47.  
  48. #include "xv.h"
  49.  
  50. #define    MAX_CMAP_SIZE    256
  51. #define    COLOR_DEPTH    8
  52. #define    MAX_COLOR    256
  53. #define    B_DEPTH        5        /* # bits/pixel to use */
  54. #define    B_LEN        (1<<B_DEPTH)
  55. #define    C_DEPTH        2
  56. #define    C_LEN        (1<<C_DEPTH)    /* # cells/color to use */
  57.  
  58. typedef    struct colorbox {
  59.   struct colorbox *next, *prev;
  60.   int              rmin,rmax, gmin,gmax, bmin,bmax;
  61.   int              total;
  62. } CBOX;
  63.  
  64. typedef struct {
  65.   int num_ents;
  66.   int entries[MAX_CMAP_SIZE][2];
  67. } CCELL;
  68.  
  69. static byte *pic24;
  70. static int   num_colors, WIDE, HIGH;
  71. static int   histogram[B_LEN][B_LEN][B_LEN];
  72.  
  73. CBOX   *freeboxes, *usedboxes;
  74. CCELL **ColorCells;
  75.  
  76. static void   get_histogram();
  77. static CBOX  *largest_box();
  78. static void   splitbox();
  79. static void   shrinkbox();
  80. static void   assign_color();
  81. static CCELL *create_colorcell();
  82. static void   map_colortable();
  83. static int    quant_fsdither();
  84. static int    Quick24to8();
  85. static int    QuickCheck();
  86.  
  87. static int    tbl1[512],     /* tables used in F-S Dithering */
  88.               tbl3[512],     /* contain i/16, 3i/16, 5i/16, 7i/16, */
  89.               tbl5[512],     /* (i=-256..255) respectively */
  90.               tbl7[512];
  91.  
  92.  
  93. /****************************/
  94. void Init24to8()
  95. /****************************/
  96. {
  97.   /* initialize Floyd-Steinberg division tables */
  98.   /* make sure rounding is done correctly for negative values! */
  99.  
  100.   int i;
  101.  
  102.   for (i = -256; i < 0; i++) {
  103.     tbl1[i+256] = -((8 -i  )/16);
  104.     tbl3[i+256] = -((8 -3*i)/16);
  105.     tbl5[i+256] = -((8 -5*i)/16);
  106.     tbl7[i+256] = -((8 -7*i)/16);
  107.   }
  108.  
  109.   for (i = 0; i < 256; i++) {
  110.     tbl1[i+256] = (i  +8)/16;
  111.     tbl3[i+256] = (3*i+8)/16;
  112.     tbl5[i+256] = (5*i+8)/16;
  113.     tbl7[i+256] = (7*i+8)/16;
  114.   }
  115. }
  116.  
  117.  
  118.  
  119. /****************************/
  120. int Conv24to8(p,w,h,nc)
  121. /****************************/
  122. byte *p;
  123. int   w,h,nc;
  124. {
  125.   int   i;
  126.   CBOX *box_list, *ptr;
  127.  
  128.   /* copy arguments to local-global variables */
  129.   pic24 = p;  pWIDE = WIDE = w;  pHIGH = HIGH = h;  num_colors = nc;
  130.  
  131.  
  132.   /* allocate pic immediately, so that if we can't allocate it, we don't
  133.      waste time running this algorithm */
  134.  
  135.   pic = (byte *) malloc(WIDE * HIGH);
  136.   if (pic == NULL) {
  137.     fprintf(stderr,"%s: Conv24to8() - failed to allocate 'pic'\n",cmd);
  138.     return(1);
  139.   }
  140.  
  141.  
  142.   /* quick check:  if we're going to display a greyscale or 1-bit image,
  143.      DON'T run this annoyingly time-consuming code.  Just convert the 24-bit
  144.      color image to an 8-bit greyscale.  This takes virtually no time, by
  145.      comparision, and it has the same effect. */
  146.  
  147.   if (mono /* || nc==0 */) {
  148.     byte *pp, *p24;
  149.  
  150.     for (i=0; i<256; i++) r[i]=g[i]=b[i]=i;   /* greyscale colormap */
  151.     pp = pic;  p24 = pic24;
  152.     for (i=WIDE*HIGH; i>0; i--, pp++, p24+=3) 
  153.       *pp = (p24[0]*11 + p24[1]*16 + p24[2]*5) >> 5;  /* pp=.33R+.5G+.17B */
  154.  
  155.     return(0);
  156.   }
  157.  
  158.   if (!noqcheck && QuickCheck(pic24,w,h,nc)) { 
  159.     /* see if it's a <256 color RGB pic */
  160.     SetISTR(ISTR_INFO,"No color compression was necessary.\n");
  161.     return 0;   
  162.   }
  163.   else if (!slow24) {
  164.     SetISTR(ISTR_INFO,"Doing quick 24-bit to 8-bit conversion.");
  165.     return(Quick24to8(pic24,w,h));
  166.   }
  167.   else 
  168.     SetISTR(ISTR_INFO,"Doing full 24-bit to 8-bit conversion.");
  169.  
  170.  
  171.   /**** STEP 1:  create empty boxes ****/
  172.  
  173.   usedboxes = NULL;
  174.   box_list = freeboxes = (CBOX *) malloc(num_colors * sizeof(CBOX));
  175.  
  176.   if (box_list == NULL) {
  177.     fprintf(stderr,"%s: Conv24to8() - failed to allocate 'freeboxes'\n",cmd);
  178.     return(1);
  179.   }
  180.  
  181.   for (i=0; i<num_colors; i++) {
  182.     freeboxes[i].next = &freeboxes[i+1];
  183.     freeboxes[i].prev = &freeboxes[i-1];
  184.   }
  185.   freeboxes[0].prev = NULL;
  186.   freeboxes[num_colors-1].next = NULL;
  187.  
  188.  
  189.   /**** STEP 2: get histogram, initialize first box ****/
  190.  
  191.   ptr = freeboxes;
  192.   freeboxes = ptr->next;
  193.   if (freeboxes) freeboxes->prev = NULL;
  194.  
  195.   ptr->next = usedboxes;
  196.   usedboxes = ptr;
  197.   if (ptr->next) ptr->next->prev = ptr;
  198.     
  199.   get_histogram(ptr);
  200.  
  201.  
  202.   /**** STEP 3: continually subdivide boxes until no more free boxes remain */
  203.  
  204.   while (freeboxes) {
  205.     ptr = largest_box();
  206.     if (ptr) splitbox(ptr);
  207.     else break;
  208.   }
  209.  
  210.   
  211.   /**** STEP 4: assign colors to all boxes ****/
  212.  
  213.   for (i=0, ptr=usedboxes; i<num_colors && ptr; i++, ptr=ptr->next) {
  214.     assign_color(ptr, &r[i], &g[i], &b[i]);
  215.   }
  216.  
  217.   /* We're done with the boxes now */
  218.   num_colors = i;
  219.   free(box_list);
  220.   box_list = freeboxes = usedboxes = NULL;
  221.  
  222.  
  223.   /**** STEP 5: scan histogram and map all values to closest color */
  224.  
  225.   /* 5a: create cell list as described in Heckbert[2] */
  226.  
  227.   ColorCells = (CCELL **) calloc(C_LEN*C_LEN*C_LEN, sizeof(CCELL *));
  228.  
  229.  
  230.   /* 5b: create mapping from truncated pixel space to color table entries */
  231.  
  232.   map_colortable();
  233.  
  234.  
  235.   /**** STEP 6: scan image, match input values to table entries */
  236.  
  237.   i=quant_fsdither();
  238.  
  239.   /* free everything that can be freed */
  240.   free(ColorCells);
  241.  
  242.   return i;
  243. }
  244.  
  245.  
  246. /****************************/
  247. static void get_histogram(box)
  248.      CBOX *box;
  249. /****************************/
  250. {
  251.   int   i,j,r,g,b,*ptr;
  252.   byte *p;
  253.  
  254.   box->rmin = box->gmin = box->bmin = 999;
  255.   box->rmax = box->gmax = box->bmax = -1;
  256.   box->total = WIDE * HIGH;
  257.  
  258.   /* zero out histogram */
  259.   ptr = &histogram[0][0][0];
  260.   for (i=B_LEN*B_LEN*B_LEN; i>0; i-- )  *ptr++ = 0;
  261.  
  262.   /* calculate histogram */
  263.   p = pic24;
  264.   for (i=0; i<HIGH; i++)
  265.     for (j=0; j<WIDE; j++) {
  266.       r = (*p++) >> (COLOR_DEPTH-B_DEPTH);
  267.       g = (*p++) >> (COLOR_DEPTH-B_DEPTH);
  268.       b = (*p++) >> (COLOR_DEPTH-B_DEPTH);
  269.  
  270.       if (r < box->rmin) box->rmin = r;
  271.       if (r > box->rmax) box->rmax = r;
  272.  
  273.       if (g < box->gmin) box->gmin = g;
  274.       if (g > box->gmax) box->gmax = g;
  275.  
  276.       if (b < box->bmin) box->bmin = b;
  277.       if (b > box->bmax) box->bmax = b;
  278.       histogram[r][g][b]++;
  279.     }
  280. }
  281.  
  282.  
  283.  
  284. /******************************/
  285. static CBOX *largest_box()
  286. /******************************/
  287. {
  288.   CBOX *tmp, *ptr;
  289.   int   size = -1;
  290.  
  291.   tmp = usedboxes;
  292.   ptr = NULL;
  293.  
  294.   while (tmp) {
  295.     if ( (tmp->rmax > tmp->rmin  ||
  296.       tmp->gmax > tmp->gmin  ||
  297.       tmp->bmax > tmp->bmin)  &&  tmp->total > size ) {
  298.       ptr = tmp;
  299.       size = tmp->total;
  300.     }
  301.     tmp = tmp->next;
  302.   }
  303.   return(ptr);
  304. }
  305.  
  306.  
  307.  
  308. /******************************/
  309. static void splitbox(ptr)
  310.      CBOX *ptr;
  311. /******************************/
  312. {
  313.   int   hist2[B_LEN], first, last, i, rdel, gdel, bdel;
  314.   CBOX *new;
  315.   int  *iptr, *histp, ir, ig, ib;
  316.   int  rmin,rmax,gmin,gmax,bmin,bmax;
  317.   enum {RED,GREEN,BLUE} which;
  318.  
  319.   /*
  320.    * see which axis is the largest, do a histogram along that
  321.    * axis.  Split at median point.  Contract both new boxes to
  322.    * fit points and return
  323.    */
  324.  
  325.   first = last = 0;   /* shut RT hcc compiler up */
  326.  
  327.   rmin = ptr->rmin;  rmax = ptr->rmax;
  328.   gmin = ptr->gmin;  gmax = ptr->gmax;
  329.   bmin = ptr->bmin;  bmax = ptr->bmax;
  330.  
  331.   rdel = rmax - rmin;
  332.   gdel = gmax - gmin;
  333.   bdel = bmax - bmin;
  334.  
  335.   if      (rdel>=gdel && rdel>=bdel) which = RED;
  336.   else if (gdel>=bdel)               which = GREEN;
  337.   else                               which = BLUE;
  338.  
  339.   /* get histogram along longest axis */
  340.   switch (which) {
  341.  
  342.   case RED:
  343.     histp = &hist2[rmin];
  344.     for (ir=rmin; ir<=rmax; ir++) {
  345.       *histp = 0;
  346.       for (ig=gmin; ig<=gmax; ig++) {
  347.     iptr = &histogram[ir][ig][bmin];
  348.     for (ib=bmin; ib<=bmax; ib++) {
  349.       *histp += *iptr;
  350.       ++iptr;
  351.     }
  352.       }
  353.       ++histp;
  354.     }
  355.     first = rmin;  last = rmax;
  356.     break;
  357.  
  358.   case GREEN:
  359.     histp = &hist2[gmin];
  360.     for (ig=gmin; ig<=gmax; ig++) {
  361.       *histp = 0;
  362.       for (ir=rmin; ir<=rmax; ir++) {
  363.     iptr = &histogram[ir][ig][bmin];
  364.     for (ib=bmin; ib<=bmax; ib++) {
  365.       *histp += *iptr;
  366.       ++iptr;
  367.     }
  368.       }
  369.       ++histp;
  370.     }
  371.     first = gmin;  last = gmax;
  372.     break;
  373.  
  374.   case BLUE:
  375.     histp = &hist2[bmin];
  376.     for (ib=bmin; ib<=bmax; ib++) {
  377.       *histp = 0;
  378.       for (ir=rmin; ir<=rmax; ir++) {
  379.     iptr = &histogram[ir][gmin][ib];
  380.     for (ig=gmin; ig<=gmax; ig++) {
  381.       *histp += *iptr;
  382.       iptr += B_LEN;
  383.     }
  384.       }
  385.       ++histp;
  386.     }
  387.     first = bmin;  last = bmax;
  388.     break;
  389.   }
  390.  
  391.  
  392.   /* find median point */
  393.   {
  394.     int sum, sum2;
  395.  
  396.     histp = &hist2[first];
  397.  
  398.     sum2 = ptr->total/2;
  399.     histp = &hist2[first];
  400.     sum = 0;
  401.         
  402.     for (i=first; i<=last && (sum += *histp++)<sum2; i++);
  403.     if (i==first) i++;
  404.   }
  405.  
  406.  
  407.   /* Create new box, re-allocate points */
  408.   
  409.   new = freeboxes;
  410.   freeboxes = new->next;
  411.   if (freeboxes) freeboxes->prev = NULL;
  412.  
  413.   if (usedboxes) usedboxes->prev = new;
  414.   new->next = usedboxes;
  415.   usedboxes = new;
  416.  
  417.   {
  418.     int sum1,sum2,j;
  419.     
  420.     histp = &hist2[first];
  421.     sum1 = 0;
  422.     for (j = first; j < i; ++j) sum1 += *histp++;
  423.     sum2 = 0;
  424.     for (j = i; j <= last; ++j) sum2 += *histp++;
  425.     new->total = sum1;
  426.     ptr->total = sum2;
  427.   }
  428.  
  429.  
  430.   new->rmin = rmin;  new->rmax = rmax;
  431.   new->gmin = gmin;  new->gmax = gmax;
  432.   new->bmin = bmin;  new->bmax = bmax;
  433.  
  434.   switch (which) {
  435.   case RED:    new->rmax = i-1;  ptr->rmin = i;  break;
  436.   case GREEN:  new->gmax = i-1;  ptr->gmin = i;  break;
  437.   case BLUE:   new->bmax = i-1;  ptr->bmin = i;  break;
  438.   }
  439.  
  440.   shrinkbox(new);
  441.   shrinkbox(ptr);
  442. }
  443.  
  444.  
  445. /****************************/
  446. static void shrinkbox(box)
  447.      CBOX *box;
  448. /****************************/
  449. {
  450.   int *histp,ir,ig,ib;
  451.   int  rmin,rmax,gmin,gmax,bmin,bmax;
  452.  
  453.   rmin = box->rmin;  rmax = box->rmax;
  454.   gmin = box->gmin;  gmax = box->gmax;
  455.   bmin = box->bmin;  bmax = box->bmax;
  456.  
  457.   if (rmax>rmin) {
  458.     for (ir=rmin; ir<=rmax; ir++)
  459.       for (ig=gmin; ig<=gmax; ig++) {
  460.     histp = &histogram[ir][ig][bmin];
  461.     for (ib=bmin; ib<=bmax; ib++)
  462.       if (*histp++ != 0) {
  463.         box->rmin = rmin = ir;
  464.         goto have_rmin;
  465.       }
  466.       }
  467.  
  468.   have_rmin:
  469.     if (rmax>rmin)
  470.       for (ir=rmax; ir>=rmin; --ir)
  471.     for (ig=gmin; ig<=gmax; ig++) {
  472.       histp = &histogram[ir][ig][bmin];
  473.       for (ib=bmin; ib<=bmax; ib++)
  474.         if (*histp++ != 0) {
  475.           box->rmax = rmax = ir;
  476.           goto have_rmax;
  477.         }
  478.     }
  479.   }
  480.  
  481.  
  482.  have_rmax:
  483.  
  484.   if (gmax>gmin) {
  485.     for (ig=gmin; ig<=gmax; ig++)
  486.       for (ir=rmin; ir<=rmax; ir++) {
  487.     histp = &histogram[ir][ig][bmin];
  488.     for (ib=bmin; ib<=bmax; ib++)
  489.       if (*histp++ != 0) {
  490.         box->gmin = gmin = ig;
  491.         goto have_gmin;
  492.       }
  493.       }
  494.   have_gmin:
  495.     if (gmax>gmin)
  496.       for (ig=gmax; ig>=gmin; --ig)
  497.     for (ir=rmin; ir<=rmax; ir++) {
  498.       histp = &histogram[ir][ig][bmin];
  499.       for (ib=bmin; ib<=bmax; ib++)
  500.         if (*histp++ != 0) {
  501.           box->gmax = gmax = ig;
  502.           goto have_gmax;
  503.         }
  504.     }
  505.   }
  506.  
  507.  
  508.  have_gmax:
  509.  
  510.   if (bmax>bmin) {
  511.     for (ib=bmin; ib<=bmax; ib++)
  512.       for (ir=rmin; ir<=rmax; ir++) {
  513.     histp = &histogram[ir][gmin][ib];
  514.     for (ig=gmin; ig<=gmax; ig++) {
  515.       if (*histp != 0) {
  516.         box->bmin = bmin = ib;
  517.         goto have_bmin;
  518.       }
  519.       histp += B_LEN;
  520.     }
  521.       }
  522.   have_bmin:
  523.     if (bmax>bmin)
  524.       for (ib=bmax; ib>=bmin; --ib)
  525.     for (ir=rmin; ir<=rmax; ir++) {
  526.       histp = &histogram[ir][gmin][ib];
  527.       for (ig=gmin; ig<=gmax; ig++) {
  528.         if (*histp != 0) {
  529.           bmax = ib;
  530.           goto have_bmax;
  531.         }
  532.         histp += B_LEN;
  533.       }
  534.     }
  535.   }
  536.  
  537.  have_bmax: return;
  538. }
  539.  
  540.  
  541.  
  542. /*******************************/
  543. static void assign_color(ptr,rp,gp,bp)
  544.      CBOX *ptr;
  545.      byte *rp,*gp,*bp;
  546. /*******************************/
  547. {
  548.   /* +1 ensures that color represents the middle of the box */
  549.   *rp = ((ptr->rmin + ptr->rmax + 1) << (COLOR_DEPTH - B_DEPTH)) / 2;
  550.   *gp = ((ptr->gmin + ptr->gmax + 1) << (COLOR_DEPTH - B_DEPTH)) / 2;
  551.   *bp = ((ptr->bmin + ptr->bmax + 1) << (COLOR_DEPTH - B_DEPTH)) / 2;
  552. }
  553.  
  554.  
  555.  
  556. /*******************************/
  557. static CCELL *create_colorcell(r1,g1,b1)
  558.      int r1,g1,b1;
  559. /*******************************/
  560. {
  561.   register int    i,tmp, dist;
  562.   register CCELL *ptr;
  563.   register byte  *rp,*gp,*bp;
  564.   int             ir,ig,ib, mindist;
  565.  
  566.   ir = r1 >> (COLOR_DEPTH-C_DEPTH);
  567.   ig = g1 >> (COLOR_DEPTH-C_DEPTH);
  568.   ib = b1 >> (COLOR_DEPTH-C_DEPTH);
  569.  
  570.   r1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
  571.   g1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
  572.   b1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
  573.  
  574.   ptr = (CCELL *) malloc(sizeof(CCELL));
  575.   *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
  576.   ptr->num_ents = 0;
  577.  
  578.   /* step 1: find all colors inside this cell, while we're at
  579.      it, find distance of centermost point to furthest
  580.      corner */
  581.  
  582.   mindist = 99999999;
  583.  
  584.   rp=r;  gp=g;  bp=b;
  585.   for (i=0; i<num_colors; i++,rp++,gp++,bp++)
  586.     if( *rp>>(COLOR_DEPTH-C_DEPTH) == ir  &&
  587.         *gp>>(COLOR_DEPTH-C_DEPTH) == ig  &&
  588.         *bp>>(COLOR_DEPTH-C_DEPTH) == ib) {
  589.  
  590.       ptr->entries[ptr->num_ents][0] = i;
  591.       ptr->entries[ptr->num_ents][1] = 0;
  592.       ++ptr->num_ents;
  593.  
  594.       tmp = *rp - r1;
  595.       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
  596.       dist = tmp*tmp;
  597.  
  598.       tmp = *gp - g1;
  599.       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
  600.       dist += tmp*tmp;
  601.  
  602.       tmp = *bp - b1;
  603.       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
  604.       dist += tmp*tmp;
  605.  
  606.       if (dist < mindist) mindist = dist;
  607.     }
  608.  
  609.  
  610.   /* step 3: find all points within that distance to box */
  611.  
  612.   rp=r;  gp=g;  bp=b;
  613.   for (i=0; i<num_colors; i++,rp++,gp++,bp++)
  614.     if (*rp >> (COLOR_DEPTH-C_DEPTH) != ir  ||
  615.     *gp >> (COLOR_DEPTH-C_DEPTH) != ig  ||
  616.     *bp >> (COLOR_DEPTH-C_DEPTH) != ib) {
  617.  
  618.       dist = 0;
  619.  
  620.       if ((tmp = r1 - *rp)>0 || (tmp = *rp - (r1 + MAX_COLOR/C_LEN-1)) > 0 )
  621.     dist += tmp*tmp;
  622.  
  623.       if( (tmp = g1 - *gp)>0 || (tmp = *gp - (g1 + MAX_COLOR/C_LEN-1)) > 0 )
  624.     dist += tmp*tmp;
  625.  
  626.       if( (tmp = b1 - *bp)>0 || (tmp = *bp - (b1 + MAX_COLOR/C_LEN-1)) > 0 )
  627.     dist += tmp*tmp;
  628.  
  629.       if( dist < mindist ) {
  630.     ptr->entries[ptr->num_ents][0] = i;
  631.     ptr->entries[ptr->num_ents][1] = dist;
  632.     ++ptr->num_ents;
  633.       }
  634.     }
  635.  
  636.  
  637.   /* sort color cells by distance, use cheap exchange sort */
  638.   {
  639.     int n, next_n;
  640.  
  641.     n = ptr->num_ents - 1;
  642.     while (n>0) {
  643.       next_n = 0;
  644.       for (i=0; i<n; ++i) {
  645.     if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
  646.       tmp = ptr->entries[i][0];
  647.       ptr->entries[i][0] = ptr->entries[i+1][0];
  648.       ptr->entries[i+1][0] = tmp;
  649.       tmp = ptr->entries[i][1];
  650.       ptr->entries[i][1] = ptr->entries[i+1][1];
  651.       ptr->entries[i+1][1] = tmp;
  652.       next_n = i;
  653.     }
  654.       }
  655.       n = next_n;
  656.     }
  657.   }
  658.   return (ptr);
  659. }
  660.  
  661.  
  662.  
  663.  
  664. /***************************/
  665. static void map_colortable()
  666. /***************************/
  667. {
  668.   int    ir,ig,ib, *histp;
  669.   CCELL *cell;
  670.  
  671.   histp  = &histogram[0][0][0];
  672.   for (ir=0; ir<B_LEN; ir++)
  673.     for (ig=0; ig<B_LEN; ig++)
  674.       for (ib=0; ib<B_LEN; ib++) {
  675.     if (*histp==0) *histp = -1;
  676.     else {
  677.       int    i, j, tmp, d2, dist;
  678.       
  679.       cell = *(ColorCells +
  680.            ( ((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
  681.            + ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH)
  682.            +  (ib>>(B_DEPTH-C_DEPTH)) ) );
  683.         
  684.       if (cell==NULL)
  685.         cell = create_colorcell(ir<<(COLOR_DEPTH-B_DEPTH),
  686.                     ig<<(COLOR_DEPTH-B_DEPTH),
  687.                     ib<<(COLOR_DEPTH-B_DEPTH));
  688.  
  689.       dist = 9999999;
  690.       for (i=0; i<cell->num_ents && dist>cell->entries[i][1]; i++) {
  691.         j = cell->entries[i][0];
  692.         d2 = r[j] - (ir << (COLOR_DEPTH-B_DEPTH));
  693.         d2 *= d2;
  694.         tmp = g[j] - (ig << (COLOR_DEPTH-B_DEPTH));
  695.         d2 += tmp*tmp;
  696.         tmp = b[j] - (ib << (COLOR_DEPTH-B_DEPTH));
  697.         d2 += tmp*tmp;
  698.         if( d2 < dist ) { dist = d2;  *histp = j; }
  699.       }
  700.     }
  701.     histp++;
  702.       }
  703. }
  704.  
  705.  
  706.  
  707. /*****************************/
  708. static int quant_fsdither()
  709. /*****************************/
  710. {
  711.   register int  *thisptr, *nextptr;
  712.   int           *thisline, *nextline, *tmpptr;
  713.   int            r1, g1, b1, r2, g2, b2;
  714.   int            i, j, imax, jmax, oval;
  715.   byte          *inptr, *outptr;
  716.   int            lastline, lastpixel;
  717.  
  718.   imax = HIGH - 1;
  719.   jmax = WIDE - 1;
  720.   
  721.   thisline = (int *) malloc(WIDE * 3 * sizeof(int));
  722.   nextline = (int *) malloc(WIDE * 3 * sizeof(int));
  723.  
  724.   if (thisline == NULL || nextline == NULL) {
  725.     fprintf(stderr,"%s: unable to allocate stuff for the 'dither' routine\n",
  726.         cmd);
  727.     return 1;
  728.   }
  729.  
  730.  
  731.   inptr  = (byte *) pic24;
  732.   outptr = (byte *) pic;
  733.  
  734.   /* get first line of picture */
  735.   for (j=WIDE * 3, tmpptr=nextline; j; j--)
  736.     *tmpptr++ = (int) *inptr++;
  737.  
  738.   for (i=0; i<HIGH; i++) {
  739.     /* swap thisline and nextline */
  740.     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;
  741.     lastline = (i==imax);
  742.  
  743.     if ((i&0x1f) == 0) WaitCursor();
  744.  
  745.     /* read in next line */
  746.     if (!lastline)
  747.       for (j=WIDE * 3, tmpptr=nextline; j; j--)
  748.     *tmpptr++ = (int) *inptr++;
  749.  
  750.     /* dither this line and put it into the output picture */
  751.     thisptr = thisline;  nextptr = nextline;
  752.  
  753.     for (j=0; j<WIDE; j++) {
  754.       lastpixel = (j==jmax);
  755.  
  756.       r2 = *thisptr++;  g2 = *thisptr++;  b2 = *thisptr++;
  757.  
  758.       if (r2<0) r2=0;  else if (r2>=MAX_COLOR) r2=MAX_COLOR-1;
  759.       if (g2<0) g2=0;  else if (g2>=MAX_COLOR) g2=MAX_COLOR-1;
  760.       if (b2<0) b2=0;  else if (b2>=MAX_COLOR) b2=MAX_COLOR-1;
  761.  
  762.       r1 = r2;  g1 = g2;  b1 = b2;
  763.  
  764.       r2 >>= (COLOR_DEPTH-B_DEPTH);
  765.       g2 >>= (COLOR_DEPTH-B_DEPTH);
  766.       b2 >>= (COLOR_DEPTH-B_DEPTH);
  767.  
  768.       if ( (oval=histogram[r2][g2][b2]) == -1) {
  769.     int ci, cj, dist, d2, tmp;
  770.     CCELL *cell;
  771.  
  772.     cell = *( ColorCells + 
  773.         ( ((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
  774.             + ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH )
  775.         +  (b2>>(B_DEPTH-C_DEPTH)) ) );
  776.           
  777.     if (cell==NULL) cell = create_colorcell(r1,g1,b1);
  778.  
  779.     dist = 9999999;
  780.     for (ci=0; ci<cell->num_ents && dist>cell->entries[ci][1]; ci++) {
  781.       cj = cell->entries[ci][0];
  782.       d2 = (r[cj] >> (COLOR_DEPTH-B_DEPTH)) - r2;
  783.       d2 *= d2;
  784.       tmp = (g[cj] >> (COLOR_DEPTH-B_DEPTH)) - g2;
  785.       d2 += tmp*tmp;
  786.       tmp = (b[cj] >> (COLOR_DEPTH-B_DEPTH)) - b2;
  787.       d2 += tmp*tmp;
  788.       if (d2<dist) { dist = d2;  oval = cj; }
  789.     }
  790.     histogram[r2][g2][b2] = oval;
  791.       }
  792.  
  793.       *outptr++ = oval;
  794.  
  795.       r1 -= r[oval];  g1 -= g[oval];  b1 -= b[oval];
  796.  
  797.       r1 += 256;              /* make positive for table indexing */
  798.       g1 += 256;
  799.       b1 += 256;
  800.  
  801.       if (!lastpixel) {
  802.     thisptr[0] += tbl7[r1];
  803.     thisptr[1] += tbl7[g1];
  804.     thisptr[2] += tbl7[b1];
  805.       }
  806.  
  807.       if (!lastline) {
  808.     if (j) {
  809.       nextptr[-3] += tbl3[r1];
  810.       nextptr[-2] += tbl3[g1];
  811.       nextptr[-1] += tbl3[b1];
  812.     }
  813.  
  814.     nextptr[0] += tbl5[r1];
  815.     nextptr[1] += tbl5[g1];
  816.     nextptr[2] += tbl5[b1];
  817.  
  818.     if (!lastpixel) {
  819.       nextptr[3] += tbl1[r1];
  820.       nextptr[4] += tbl1[g1];
  821.       nextptr[5] += tbl1[b1];
  822.     }
  823.     nextptr += 3;
  824.       }
  825.     }
  826.   }
  827.   free(thisline);  free(nextline);
  828.   return 0;
  829. }
  830.  
  831.  
  832.  
  833.  
  834.  
  835. /************************************/
  836. static int Quick24to8(p24,w,h)
  837. byte *p24;
  838. int   w,h;
  839. {
  840.  
  841.   /* floyd-steinberg dithering.
  842.    *
  843.    * ----   x    7/16
  844.    * 3/16  5/16  1/16
  845.    *
  846.    */
  847.  
  848.   /* called after 'pic' has been alloced, pWIDE,pHIGH set up, mono/1-bit
  849.      checked already */
  850.  
  851.   byte *pp;
  852.   int  r1, g1, b1;
  853.   int  *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
  854.   int  i, j, val, pwide3;
  855.   int  imax, jmax;
  856.  
  857.   pp = pic;  pwide3 = w * 3;  imax = h-1;  jmax = w-1;
  858.  
  859.   /* up to 256 colors:     3 bits R, 3 bits G, 2 bits B  (RRRGGGBB) */
  860. #define RMASK 0xe0
  861. #define R_SHIFT        0
  862. #define GMASK 0xe0
  863. #define G_SHIFT        3
  864. #define BMASK 0xc0
  865. #define B_SHIFT        6
  866.  
  867.   /* load up colormap */
  868.   /* note that 0 and 255 of each color are always in the map; */
  869.   /* intermediate values are evenly spaced. */
  870.   for (i=0; i<256; i++) {
  871.     r[i] = (((i<<R_SHIFT) & RMASK) * 255 + RMASK/2) / RMASK;
  872.     g[i] = (((i<<G_SHIFT) & GMASK) * 255 + GMASK/2) / GMASK;
  873.     b[i] = (((i<<B_SHIFT) & BMASK) * 255 + BMASK/2) / BMASK;
  874.   }
  875.  
  876.  
  877.   thisline = (int *) malloc(pwide3 * sizeof(int));
  878.   nextline = (int *) malloc(pwide3 * sizeof(int));
  879.   if (!thisline || !nextline) {
  880.     fprintf(stderr,"%s: unable to allocate memory in Quick24to8()\n", cmd);
  881.     return(1);
  882.     }
  883.  
  884.   /* get first line of picture */
  885.   for (j=pwide3, tmpptr=nextline; j; j--) *tmpptr++ = (int) *p24++;
  886.  
  887.   for (i=0; i<h; i++) {
  888.     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;   /* swap */
  889.  
  890.     if ((i&0x1f) == 0) WaitCursor();
  891.  
  892.     if (i!=imax)   /* get next line */
  893.       for (j=pwide3, tmpptr=nextline; j; j--)
  894.     *tmpptr++ = (int) *p24++;
  895.  
  896.     for (j=0, thisptr=thisline, nextptr=nextline; j<w; j++,pp++) {
  897.       r1 = *thisptr++;  g1 = *thisptr++;  b1 = *thisptr++;
  898.       RANGE(r1,0,255);  RANGE(g1,0,255);  RANGE(b1,0,255);  
  899.  
  900.       /* choose actual pixel value */
  901.       val = (((r1&RMASK)>>R_SHIFT) | ((g1&GMASK)>>G_SHIFT) | 
  902.          ((b1&BMASK)>>B_SHIFT));
  903.       *pp = val;
  904.  
  905.       /* compute color errors */
  906.       r1 -= r[val];
  907.       g1 -= g[val];
  908.       b1 -= b[val];
  909.  
  910.       /* Add fractions of errors to adjacent pixels */
  911.       r1 += 256;              /* make positive for table indexing */
  912.       g1 += 256;
  913.       b1 += 256;
  914.  
  915.       if (j!=jmax) {  /* adjust RIGHT pixel */
  916.     thisptr[0] += tbl7[r1];
  917.     thisptr[1] += tbl7[g1];
  918.     thisptr[2] += tbl7[b1];
  919.       }
  920.       
  921.       if (i!=imax) {    /* do BOTTOM pixel */
  922.     nextptr[0] += tbl5[r1];
  923.     nextptr[1] += tbl5[g1];
  924.     nextptr[2] += tbl5[b1];
  925.  
  926.     if (j>0) {  /* do BOTTOM LEFT pixel */
  927.       nextptr[-3] += tbl3[r1];
  928.       nextptr[-2] += tbl3[g1];
  929.       nextptr[-1] += tbl3[b1];
  930.     }
  931.  
  932.     if (j!=jmax) {  /* do BOTTOM RIGHT pixel */
  933.       nextptr[3] += tbl1[r1];
  934.       nextptr[4] += tbl1[g1];
  935.       nextptr[5] += tbl1[b1];
  936.     }
  937.     nextptr += 3;
  938.       }
  939.     }
  940.   }
  941.  
  942.   return 0;
  943. }
  944.       
  945.  
  946.  
  947. /****************************/
  948. static int QuickCheck(pic24,w,h,maxcol)
  949. byte *pic24;
  950. int   w,h,maxcol;
  951. {
  952.   /* scans picture until it finds more than 'maxcol' different colors.  If it
  953.      finds more than 'maxcol' colors, it returns '0'.  If it DOESN'T, it does
  954.      the 24-to-8 conversion by simply sticking the colors it found into
  955.      a colormap, and changing instances of a color in pic24 into colormap
  956.      indicies (in pic) */
  957.  
  958.   unsigned long colors[256],col;
  959.   int           i, nc, low, high, mid;
  960.   byte         *p, *pix;
  961.  
  962.   if (maxcol>256) maxcol = 256;
  963.  
  964.   /* put the first color in the table by hand */
  965.   nc = 0;  mid = 0;  
  966.  
  967.   for (i=w*h,p=pic24; i; i--) {
  968.     col  = (((u_long) *p++) << 16);  
  969.     col += (((u_long) *p++) << 8);
  970.     col +=  *p++;
  971.  
  972.     /* binary search the 'colors' array to see if it's in there */
  973.     low = 0;  high = nc-1;
  974.     while (low <= high) {
  975.       mid = (low+high)/2;
  976.       if      (col < colors[mid]) high = mid - 1;
  977.       else if (col > colors[mid]) low  = mid + 1;
  978.       else break;
  979.     }
  980.  
  981.     if (high < low) { /* didn't find color in list, add it. */
  982.       /* WARNING: this is an overlapped memory copy.  memcpy doesn't do
  983.      it correctly, hence 'bcopy', which claims to */
  984.       if (nc>=maxcol) return 0;
  985.       bcopy(&colors[low], &colors[low+1], (nc - low) * sizeof(unsigned long));
  986.       colors[low] = col;
  987.       nc++;
  988.     }
  989.   }
  990.  
  991.  
  992.   /* run through the data a second time, this time mapping pixel values in
  993.      pic24 into colormap offsets into 'colors' */
  994.  
  995.   for (i=w*h,p=pic24, pix=pic; i; i--,pix++) {
  996.     col  = (((u_long) *p++) << 16);  
  997.     col += (((u_long) *p++) << 8);
  998.     col +=  *p++;
  999.  
  1000.     /* binary search the 'colors' array.  It *IS* in there */
  1001.     low = 0;  high = nc-1;
  1002.     while (low <= high) {
  1003.       mid = (low+high)/2;
  1004.       if      (col < colors[mid]) high = mid - 1;
  1005.       else if (col > colors[mid]) low  = mid + 1;
  1006.       else break;
  1007.     }
  1008.  
  1009.     if (high < low) {
  1010.       fprintf(stderr,"QuickCheck:  impossible!\n");
  1011.       exit(1);
  1012.     }
  1013.     *pix = mid;
  1014.   }
  1015.  
  1016.   /* and load up the 'desired colormap' */
  1017.   for (i=0; i<nc; i++) {
  1018.     r[i] =  colors[i]>>16;  
  1019.     g[i] = (colors[i]>>8) & 0xff;
  1020.     b[i] =  colors[i]     & 0xff;
  1021.   }
  1022.  
  1023.   return 1;
  1024. }
  1025.